A typical search engine indexing algorithm utilizes an inverted index data structure. This is conceptually similar to the index in the back of a book; it is an index data structure mapping content, such as a list of words, to its location in a document (or set of documents). In the context of a search engine, the documents are commonly web pages, e-mail messages, and the like. The occurrence of a word in a document may be called a posting, and the list of all documents containing a word may be called a posting list. Just as a book index entry lists page numbers, a posting list may contain document identification numbers (docIDs). When a search engine receives a query, it can look up the posting list for each word in the query and combines the results. In order to combine the results efficiently, the postings may be stored in order of their docIDs.
It may be desirable to store posting lists in as little space as possible. By using the differences between adjacent docIDs rather than the docIDs themselves, the postings can contain smaller numbers. There are numerous other examples, from general databases to the MIDI specification, where data might be coded more compactly and then decoded at a later point, where often the decoding happens repeatedly based on when the data may be needed. There are a variety of techniques developed for storing data in less space. However, the methods may have deficiencies including speed limitations or storage efficiency limitations.